//
//  912. 排序数组.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/8/29.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution912 {
    // 此题可以用三种排序算法来解
    // 快速排序: 选定参照值，每次将一个区域拆分成两个区，左边都小于参照值，右边都大于参照值。从另一个角度看，就是每次固定一个值的位置
    // 堆排序
    // 归并排序
    func sortArray(_ nums: [Int]) -> [Int] {
        var nums = nums
        quickSort(&nums, start: 0, end: nums.count - 1)
        return nums
    }
    func quickSort(_ nums: inout [Int], start: Int, end: Int) {
        guard start < end else {
            return
        }
        let mid = partition(&nums, start: start, end: end)
        quickSort(&nums, start: start, end: mid - 1)
        quickSort(&nums, start: mid + 1, end: end)
    }
    func partition(_ nums: inout [Int], start: Int, end: Int) -> Int {
        let pivot = end
        var counter = start
        for i in start...end {
            if nums[i] < nums[pivot] {
                let tmp = nums[counter]
                nums[counter] = nums[i]
                nums[i] = tmp
                counter += 1
            }
        }
        let tmp = nums[counter]
        nums[counter] = nums[pivot]
        nums[pivot] = tmp
        return counter
    }
    
    // 堆排序
    // 堆排序的流程
    // 先建立大顶堆
    // 然后取出堆顶元素与最后元素交换
    // 然后将堆顶元素向下滤，
    func sortArray2(_ nums: [Int]) -> [Int] {
        var nums = nums
        // 构建大顶堆
        for i in (0..<nums.count).reversed() {
            shitDown(&nums, length: nums.count, index: i)
        }
        // 将堆顶元素取出，放到后面，再重新调整堆
        for i in (0..<nums.count).reversed() {
            let tmp = nums[0]
            nums[0] = nums[i]
            nums[i] = tmp
            // 从头开始调整，并只调整到i的length
            shitDown(&nums, length: i, index: 0)
        }
        return nums
    }
    // 下滤
    func shitDown(_ nums: inout [Int], length: Int, index: Int ) {
        let v = nums[index]
        var index = index
        // 根节点从0开始
        while index < length / 2 {
            var childIndex = index * 2 + 1
            let rightIndex = childIndex + 1
            // 如果右子节点存在，且比左要打，上移的是右
            if rightIndex < length && nums[rightIndex] > nums[childIndex] {
                childIndex = rightIndex
            }
            // 如果最大的比当前的还小。则不用移动了
            if nums[childIndex] < v {
                break
            }
            nums[index] = nums[childIndex]
            index = childIndex
        }
        nums[index] = v
    }
    // 归并排序
    // 归并排序实际上是分治法
    func sortArray3(_ nums: [Int]) -> [Int] {
        var nums = nums
        mergetSort(&nums, start: 0, end: nums.count - 1)
        return nums
    }
    // 分治
    func mergetSort(_ nums: inout [Int], start: Int, end: Int) {
        guard start < end else {
            return
        }
        let mid = (start + end) / 2
        mergetSort(&nums, start: start, end: mid)
        mergetSort(&nums, start: mid + 1, end: end)
        mergeTow(&nums, start: start, mid: mid, end: end)
    }
    // 合并两个已经有序的数组
    func mergeTow(_ nums: inout [Int], start: Int, mid: Int, end: Int) {
        var temp: [Int] = Array(repeating: 0, count: end - start + 1)
        var first = start
        var second = mid + 1
        var index = 0
        // 当其中任意一个解释时都会结束
        while first <= mid && second <= end{
            if nums[first] <= nums[second]  {
                temp[index] = nums[first]
                first += 1
            } else {
                temp[index] = nums[second]
                second += 1
            }
            index += 1
        }
        while first <= mid {
            temp[index] = nums[first]
            first += 1
            index += 1
        }
        while second <= end {
            temp[index] = nums[second]
            second += 1
            index += 1
        }
        
        for i in 0..<temp.count {
            nums[start + i] = temp[i]
        }
    }
    
    static func test() {
        let solution = Solution912()
        let nums = [5,2,3,1]
        let result = solution.sortArray3(nums)
        print(result)
    }
}
